package Heap;

import java.util.*;

class IntCmp implements Comparator<Integer> {
    public int compare(Integer o1,Integer o2) {
        return o2.compareTo(o1);
    }
}

public class TestHeap {

    public static int[] smallestK1(int[] arr,int k) {
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
        for(int i=0;i<arr.length;i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for(int i=0;i<k;i++) {
            tmp[i]=minHeap.poll();
        }
        return tmp;
    }

    public static int[] smallestK2(int[] arr,int k) {
        int[] tmp=new int[k];
        if(k==0)return tmp;
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new IntCmp());
        for(int i=0;i<k;i++) {
            maxHeap.offer(arr[i]);
        }
        for(int i=k;i<arr.length;i++) {
            int val=maxHeap.peek();
            if(val>arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for(int i=0;i<k;i++) {
            tmp[i]=maxHeap.poll();
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array={27,15,19,18,28,34,65,49,25,37};
        System.out.println(Arrays.toString(smallestK2(array, 3)));
    }

    public static void main2(String[] args) {
        List<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
//        优先队列默认是小根堆
        PriorityQueue<Integer> pq=new PriorityQueue<>(list);
        pq.offer(12);
        pq.offer(1);
        pq.offer(9);
        System.out.println(pq.peek());
    }

    public static void main1(String[] args) {
        Heap heap=new Heap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        heap.init(array);
        heap.createHeap();
        heap.offer(40);
        heap.poll();
        heap.heapSort();
    }


}
